package demo;



public class MyHashMap {

    private static class Node{
        private String key;
        private Long value;
        Node next;

        public Node(String key, long value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key='" + key + '\'' +
                    ", value=" + value +
                    '}';
        }
    }

    private Node[]array;//结点类数组
    private int size;//元素个数

    public MyHashMap() {
       this.array=new Node[8];//哈希桶的数量需要是2的n次方
        int size=0;//初始元素数量为0
    }

        public Long put(String key, long value) {
        //先取到key的合法下标
            int z = key.hashCode();//到关键码

            int index = z & (array.length - 1);//得到合法下标

        //找到要放入的链表的头结点
        Node head = array[index];
        //开始在链表上查找
        Node cur = head;

        while (cur != null) {
            if (key.equals(cur.key)) {
                //如果找到已经存在则更新value
                long oldValue = cur.value;

                cur.value = value;
                return oldValue;
            }
            cur = cur.next;
        }
        //如果没有存在则插入 头插尾插都可 这里使用头插
        Node node = new Node(key, value);
        node.next = head;
        //插入后记得更新哈希桶第一个结点
        array[index] = node;
        //找不到插入以后元素个数加一
        size++;
        //如果负载因子的值超过四分之三，那么扩容
        if((1.0*size/array.length)>=0.75) {
            grow();
        }
        return null;
    }
    //扩容操作
    public void grow(){
        int newLength=array.length*2;//扩容的哈希数也需要是2的n次方
        Node[]newArray=new Node[newLength];

        //每个元素的合法下标是与哈希桶数量有关的，哈希桶数量改变，每个元素都需要重新计算下标
        //双层循环遍历链表中的每一个元素
        for(int i=0;i<array.length;i++){

            Node head=array[i];
            Node cur=head;
            while(cur!=null){
                Node next=cur.next;//cur.next头插时需要修改，提前保存
                //重新算出当前结点的元素下标index
                int z = cur.key.hashCode();//到关键码

                int index = z & (array.length - 1);//得到合法下标

                //将原链表中的元素放入新链表
                //头插
                cur.next=newArray[index];
                newArray[index]=cur;
                cur=next;
            }
        }
        this.array=newArray;
    }

    //哈希表 get()方法 查找key-value 找到key返回value
    public Long get(String key){

        int z=key.hashCode();

        int index=z&(array.length-1);
        Node cur=array[index];
        for( ;cur!=null;cur=cur.next){
            if(key.equals(cur.key)){
                return cur.value;
            }
        }
        return null;
    }

    //哈希表 remove方法 移除 key-value  找到移除后返回对应的value 找不到返回空
    public Long remove(String key){

        int z = key.hashCode();//到关键码

        int index = z & (array.length - 1);//得到合法下标


        Node cur=array[index];
         Node prev=null;
         for(;cur!=null;prev=cur,cur=cur.next){
             if(key.equals(cur.key)){
                 //移除结点要考虑移除的是否是头结点
                 //移除之前要先保存当前结点的value
                 long oldValue=cur.value;
                 //要移除的是头结点
                 if(prev==null ){
                     array[index]=cur.next;
                     size--;
                     return oldValue;
                 }else{
                     //要移除的不是头结点
                     prev=cur.next;
                     size--;
                     return oldValue;
                 }
             }
         }
         //全部遍历如果还是没找到说明哈希表没有需要移除的元素，直接返回空
         return null;
    }

}

